package lc.q700_750;

import java.util.*;

/**
 * 给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。
 *
 * 现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。
 *
 * 合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是 按字符 ASCII 顺序排列 的邮箱地址。账户本身可以以 任意顺序 返回。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/accounts-merge
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q721 {

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        // 通过邮箱地址查找账户
        Map<String, Integer> emailToIndex = new HashMap<>();
        Map<String, String> emailToName = new HashMap<>();
        int index = 0;
        for (List<String> account : accounts) {
            String name = account.get(0);
            for (int i = 1; i < account.size(); i++) {
                String email = account.get(i);
                if (!emailToName.containsKey(email)) {
                    emailToName.put(email, name);
                    emailToIndex.put(email, index++);
                }
            }
        }
        // 对emailToName进行解析
        UnionFind unionFind = new UnionFind(index);
        // 遍历邮箱
        for (List<String> account : accounts) {
            String firstMail = account.get(1);
            int firstIndex = emailToIndex.get(firstMail);
            for (int i = 2; i < account.size(); i++) {
                // 合并后面的邮箱到同一个index
                unionFind.union(firstIndex, emailToIndex.get(account.get(i)));
            }
        }
        // 合并完成之后
        Map<Integer, List<String>> indexToMail = new HashMap<>();
        for (String email : emailToIndex.keySet()) {
            int emailIndex = unionFind.find(emailToIndex.get(email));
            List<String> orDefault = indexToMail.getOrDefault(emailIndex, new ArrayList<>());
            orDefault.add(email);
            indexToMail.put(emailIndex, orDefault);
        }
        List<List<String>> merged = new ArrayList<>();
        for (List<String> value : indexToMail.values()) {
            Collections.sort(value);
            String name = emailToName.get(value.get(0));
            List<String> account = new ArrayList<>();
            account.add(name);
            account.addAll(value);
            merged.add(account);
        }
        return merged;
    }

    class UnionFind {

        int[] parent;

        public UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public void union(int index1, int index2) {
            // 合并两个index
            parent[find(index2)] = find(index1);
        }

        public int find(int index) {
            if (index != parent[index]) {
                parent[index] = find(parent[index]);
            }
            return parent[index];
        }

    }

}
